package com.wwz.leetcode;

import org.junit.Test;
/**
 * @description: 第 k 个缺失的正整数
 * @author: Sailor
 * @date: 2023-12-20 16:15:37
 */
public class LeetCode1539 {
    @Test
    public void test() {
        int[] nums = {1, 2, 3, 4};
        System.out.println(findKthPositive2(nums, 2));
    }

    public int findKthPositive(int[] arr, int k) {
        Integer start = 1;
        int i = 0;
        while (k > 0 && i < arr.length) {
            if (start.equals(arr[i])) {
                i++;
            } else {
                k--;
            }
            if (k == 0) {
                break;
            } else {
                start += 1;
            }
        }
        if (k > 0) {
            for (int j = 1; j < k; j++) {
                start++;
            }
        }
        return start;
    }

    public int findKthPositive2(int[] arr, int k) {
        // 缺失的正整数一定 >= k
        // 数组中每出现一个 <= k 的数字, 意味着少了一个缺失的数字, 此时k+1
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= k) {
                k++;
            }
        }
        return k;
    }
}
